/****************************************************************************
 *                  fnsyntax.cpp
 *
 * This module implements the the function type used by iso surfaces and
 * the function pattern.
 *
 * This module is inspired by code by D. Skarda, T. Bily and R. Suzuki.
 *
 * from Persistence of Vision(tm) Ray Tracer version 3.6.
 * Copyright 1991-2003 Persistence of Vision Team
 * Copyright 2003-2004 Persistence of Vision Raytracer Pty. Ltd.
 *---------------------------------------------------------------------------
 * NOTICE: This source code file is provided so that users may experiment
 * with enhancements to POV-Ray and to port the software to platforms other
 * than those supported by the POV-Ray developers. There are strict rules
 * regarding how you are permitted to use this file. These rules are contained
 * in the distribution and derivative versions licenses which should have been
 * provided with this file.
 *
 * These licences may be found online, linked from the end-user license
 * agreement that is located at http://www.povray.org/povlegal.html
 *---------------------------------------------------------------------------
 * This program is based on the popular DKB raytracer version 2.12.
 * DKBTrace was originally written by David K. Buck.
 * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
 *---------------------------------------------------------------------------
 * $File: //depot/povray/3.6-release/source/fnsyntax.cpp $
 * $Revision: #2 $
 * $Change: 2939 $
 * $DateTime: 2004/07/05 03:43:26 $
 * $Author: root $
 * $Log$
 *****************************************************************************/

#include <limits.h>

#include "frame.h"
#include "povproto.h"
#include "parse.h"
#include "povray.h"
#include "tokenize.h"
#include "vector.h"
#include "function.h"
#include "fnsyntax.h"
#include "fnpovfpu.h"
#include "mathutil.h"

BEGIN_POV_NAMESPACE

/*****************************************************************************
* Static functions
******************************************************************************/

ExprNode *parse_expr();
TOKEN expr_get_token();
ExprNode *new_expr_node(int stage, int op);

bool expr_noop(ExprNode *&current, int stage, int op);
bool expr_grow(ExprNode *&current, int stage, int op);
bool expr_call(ExprNode *&current, int stage, int op);
bool expr_put(ExprNode *&current, int stage, int op);
bool expr_new(ExprNode *&current, int stage, int op);
bool expr_ret(ExprNode *&current, int stage, int op);
bool expr_err(ExprNode *&current, int stage, int op);
void optimise_expr(ExprNode *node);
void optimise_call(ExprNode *node);
bool right_subtree_has_variable_expr(ExprNode *node);
bool left_subtree_has_variable_expr(ExprNode *node);
void dump_expr(FILE *f, ExprNode *node);


/*****************************************************************************
* Local typedefs
******************************************************************************/

typedef struct
{
	int stage;
	TOKEN token;
	bool (*operation)(ExprNode *&, int, int);
	int next;
	int op;
} ExprParserTableEntry;

typedef struct
{
	int stage;
	char *expected;
} ExprParserErrorEntry;


/*****************************************************************************
* Local variables
******************************************************************************/

const ExprParserErrorEntry expr_parser_error_table[] =
{
	{ 35, "operator" },
	{ 45, "." },
	{ 40, "sign or operand" },
	{ 50, "operand" },
	{ 55, ")" },
	{ 60, "color or vector member" },
	{ -1, NULL }
};
 
const ExprParserTableEntry expr_parser_table[] =
{
	// logical or
	{  5, BAR_TOKEN,         expr_grow, 40, OP_OR       },	// 0
	// logical and
	{ 10, AMPERSAND_TOKEN,   expr_grow, 40, OP_AND      },	// 1
	// equal, not equal
	{ 15, EQUALS_TOKEN,      expr_grow, 40, OP_CMP_EQ   },	// 2
	{ 15, REL_NE_TOKEN,      expr_grow, 40, OP_CMP_NE   },	// 3
	// smaller and/or equal, greater and/or equal
	{ 15, LEFT_ANGLE_TOKEN,  expr_grow, 40, OP_CMP_LT   },	// 4
	{ 15, REL_LE_TOKEN,      expr_grow, 40, OP_CMP_LE   },	// 5
	{ 15, RIGHT_ANGLE_TOKEN, expr_grow, 40, OP_CMP_GT   },	// 6
	{ 15, REL_GE_TOKEN,      expr_grow, 40, OP_CMP_GE   },	// 7
	// plus, minus
	{ 20, PLUS_TOKEN,        expr_grow, 40, OP_ADD      },	// 8
	{ 20, DASH_TOKEN,        expr_grow, 40, OP_SUB      },	// 9
	// multiply, divide
	{ 25, STAR_TOKEN,        expr_grow, 40, OP_MUL      },	// 10
	{ 25, SLASH_TOKEN,       expr_grow, 40, OP_DIV      },	// 11
	// ')', '}' or ',' - end of function
	{ 35, RIGHT_PAREN_TOKEN, expr_ret,  -1, OP_NONE     },	// 12
	{ 35, RIGHT_CURLY_TOKEN, expr_ret,  -1, OP_NONE     },	// 13
	{ 35, COMMA_TOKEN,       expr_ret,  -1, OP_NONE     },	// 14
	{ 35, LAST_TOKEN,        expr_err,  -1, OP_NONE     },	// 15
	// vector/color member access
	{ 45, PERIOD_TOKEN,      expr_grow, 60, OP_DOT      },	// 16
	{ 45, LAST_TOKEN,        expr_err,  -1, OP_NONE     },	// 17
	// unary plus, unary minus, (logical not - disabled)
	{ 40, PLUS_TOKEN,        expr_noop, 50, OP_NONE     },	// 18
	{ 40, DASH_TOKEN,        expr_grow, 50, OP_NEG      },	// 19
	{ 40, EXCLAMATION_TOKEN, expr_err,  -1, OP_NOT      },	// 20
	// constant, variable, (expression), function
	{ 50, FLOAT_TOKEN,       expr_put,   5, OP_CONSTANT },	// 21
	{ 50, FLOAT_ID_TOKEN,    expr_put,   5, OP_VARIABLE },	// 22
	{ 50, FUNCT_ID_TOKEN,    expr_call,  5, OP_CALL     },	// 23
	{ 50, VECTFUNCT_ID_TOKEN,expr_call, 45, OP_CALL     },	// 24
	{ 50, LEFT_PAREN_TOKEN,  expr_new,  55, OP_FIRST    },	// 25
	{ 50, LAST_TOKEN,        expr_err,  -1, OP_NONE     },	// 26
	// (expression)
	{ 55, RIGHT_PAREN_TOKEN, expr_noop,  5, OP_NONE     },	// 27
	{ 55, LAST_TOKEN,        expr_err,  -1, OP_NONE     },	// 28
	// vector/color members
	{ 60, FLOAT_ID_TOKEN,    expr_put,   5, OP_MEMBER   },	// 29
	{ 60, T_TOKEN,           expr_put,   5, OP_MEMBER   },	// 30
	{ 60, RED_TOKEN,         expr_put,   5, OP_MEMBER   },	// 31
	{ 60, GREEN_TOKEN,       expr_put,   5, OP_MEMBER   },	// 32
	{ 60, BLUE_TOKEN,        expr_put,   5, OP_MEMBER   },	// 33
	{ 60, FILTER_TOKEN,      expr_put,   5, OP_MEMBER   },	// 34
	{ 60, TRANSMIT_TOKEN,    expr_put,   5, OP_MEMBER   },	// 35
	{ 60, GRAY_TOKEN,        expr_put,   5, OP_MEMBER   },	// 36
	{ 60, LAST_TOKEN,        expr_err,  -1, OP_NONE     }	// 37
};

// parse_expr has to start with first unary operator [trf]
const int START_LEFTMOST_PARSE_INDEX = 18;

/*****************************************************************************
*
* FUNCTION
*
*   FNSyntax_ParseExpression
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*
*   ExprNode - parsed expression root pointer
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Parse and optimise an expression.
*
* CHANGES
*
*   -
*
******************************************************************************/

ExprNode *FNSyntax_ParseExpression()
{
	ExprNode *expression = NULL;

	expression = parse_expr();
	optimise_expr(expression);

	return expression;
}


/*****************************************************************************
*
* FUNCTION
*
*   FNSyntax_GetTrapExpression
*
* INPUT
*
*   trap - number of the trap
*   
* OUTPUT
*   
* RETURNS
*
*   ExprNode - expression root pointer
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Generate an expression which only contains a trap.
*
* CHANGES
*
*   -
*
******************************************************************************/

ExprNode *FNSyntax_GetTrapExpression(unsigned int trap)
{
	ExprNode *expression = NULL;

	expression = new_expr_node(0, OP_TRAP);
	expression->trap = trap;

	return expression;
}


/*****************************************************************************
*
* FUNCTION
*
*   FNSyntax_DeleteExpression
*
* INPUT
*
*   node - root node of the (sub-) tree to delete
*   
* OUTPUT
*   
* RETURNS
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Delete an expression (sub-) tree.
*
* CHANGES
*
*   -
*
******************************************************************************/

void FNSyntax_DeleteExpression(ExprNode *node)
{
	ExprNode *temp = NULL;

	for(ExprNode *i = node; i != NULL; i = i->next)
	{
		if(temp != NULL)
		{
			POV_FREE(temp);
		}

		FNSyntax_DeleteExpression(i->child);

		if((i->op == OP_VARIABLE) || (i->op == OP_MEMBER))
		{
			POV_FREE(i->variable);
		}
		else if(i->op == OP_CALL)
		{
			if((i->call.token == FUNCT_ID_TOKEN) || (i->call.token == VECTFUNCT_ID_TOKEN))
				POVFPU_RemoveFunction(i->call.fn);
			POV_FREE(i->call.name);
		}

		temp = i;
	}

	if(temp != NULL)
	{
		POV_FREE(temp);
	}
}


/*****************************************************************************
*
* FUNCTION
*
*   parse_expr
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*
*   ExprNode - parsed expression root pointer
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Parse an expression or subexpression.
*
* CHANGES
*
*   -
*
******************************************************************************/

ExprNode *parse_expr()
{
	ExprNode *current = NULL;
	ExprNode *node = NULL;
	TOKEN token;
	int start_index;
	int i;

	current = node = new_expr_node(0, OP_FIRST);

	start_index = START_LEFTMOST_PARSE_INDEX;
	token = expr_get_token();

	while(true)
	{
		// search for matching token
		for(i = start_index; ; i++)
		{
			if((expr_parser_table[i].token == token) ||
			   (expr_parser_table[i].token == LAST_TOKEN))
				break;
		}

		// execute operation
		if(expr_parser_table[i].operation(current, expr_parser_table[i].stage, expr_parser_table[i].op) == false)
			break;

		// find next index start
		if(expr_parser_table[i].next >= 0)
		{
			if(expr_parser_table[i].next < expr_parser_table[i].stage)
				start_index = 0;
			// searching the whole table allows forward references
			// to stages with a lower stage number [trf]
			while(expr_parser_table[start_index].stage != expr_parser_table[i].next)
				start_index++;
		}

		token = expr_get_token();
	}

	return node;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_get_token
*
* INPUT
*   
* OUTPUT
*   
* RETURNS
*
*   TOKEN - simplified token from Get_Token
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Gets a token and simplifies it for use by the expression parser.
*
* CHANGES
*
*   -
*
******************************************************************************/

TOKEN expr_get_token()
{
	Get_Token();

	if(Token.Function_Id == X_TOKEN)
		return FLOAT_ID_TOKEN;
	else if(Token.Function_Id == Y_TOKEN)
		return FLOAT_ID_TOKEN;
	else if(Token.Function_Id == Z_TOKEN)
		return FLOAT_ID_TOKEN;
	else if(Token.Function_Id == U_TOKEN)
		return FLOAT_ID_TOKEN;
	else if(Token.Function_Id == V_TOKEN)
		return FLOAT_ID_TOKEN;
	else if(Token.Function_Id == IDENTIFIER_TOKEN)
		return FLOAT_ID_TOKEN;
	else if(Token.Function_Id == CLOCK_TOKEN)
	{
		Token.Token_Float = opts.FrameSeq.Clock_Value;
		return FLOAT_TOKEN;
	}
	else if(Token.Function_Id == PI_TOKEN)
	{
		Token.Token_Float = M_PI;
		return FLOAT_TOKEN;
	}
	else if(Token.Function_Id == RED_TOKEN)
		return RED_TOKEN;
	else if(Token.Function_Id == GREEN_TOKEN)
		return GREEN_TOKEN;
	else if(Token.Function_Id == BLUE_TOKEN)
		return BLUE_TOKEN;
	else if(Token.Function_Id == FILTER_TOKEN)
		return FILTER_TOKEN;
	else if(Token.Function_Id == TRANSMIT_TOKEN)
		return TRANSMIT_TOKEN;
	else if(Token.Function_Id == T_TOKEN)
		return T_TOKEN;
	else if(Token.Function_Id == GRAY_TOKEN)
		return GRAY_TOKEN;

	if(Token.Token_Id == FLOAT_FUNCT_TOKEN)
	{
		if(Token.Function_Id == FLOAT_TOKEN)
			return FLOAT_TOKEN;
		else if(Token.Function_Id == FLOAT_ID_TOKEN)
		{
			Token.Token_Float = *((DBL *)Token.Data);
			return FLOAT_TOKEN;
		}

		return FUNCT_ID_TOKEN;
	}

	return Token.Token_Id;
}


/*****************************************************************************
*
* FUNCTION
*
*   new_expr_node
*
* INPUT
*
*   stage - stage/precedence of new node
*   op - operation of new node
*   
* OUTPUT
*   
* RETURNS
*
*   ExprNode - new expression node structure
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Creates a new expression node structure.
*
* CHANGES
*
*   -
*
******************************************************************************/

ExprNode *new_expr_node(int stage, int op)
{
	ExprNode *node = NULL;

	node = (ExprNode *)POV_MALLOC(sizeof(ExprNode), "ExprNode");
	node->parent = NULL;
	node->child = NULL;
	node->prev = NULL;
	node->next = NULL;
	node->stage = stage;
	node->op = op;

	return node;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_noop
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that does nothing.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_noop(ExprNode *&, int, int)
{
	return true;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_grow
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that grows the tree in the
*   correct place based on the stage/level of the other nodes in the tree.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_grow(ExprNode *&current, int stage, int op)
{
	ExprNode *node = NULL;

	if(current == NULL)
		return false;

	// the idea is this order: current, node, current->child
	if(current->stage < stage)
	{
		while(current->child != NULL)
		{
			if(current->child->stage > stage)
				break;

			current = current->child;

			if(current->stage == stage)
				break;
		}
	}
	else if(current->stage > stage)
	{
		while(current->parent != NULL)
		{
			current = current->parent;

			if(current->stage <= stage)
				break;
		}
	}

	if(current->stage == stage)
	{
		while(current->next != NULL)
			current = current->next;

		node = new_expr_node(stage, op);

		node->parent = current->parent; 
		node->prev = current;
		current->next = node;

		current = node;
	}
	else
	{
		node = new_expr_node(stage, OP_LEFTMOST);

		node->parent = current;
		node->child = current->child;
		current->child = node;
		for(ExprNode *ptr = node->child; ptr != NULL; ptr = ptr->next)
			ptr->parent = node;

		current = new_expr_node(stage, op);
		current->prev = node;
		node->next = current;
		current->parent = node->parent;
	}

	return true;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_call
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that handles a function call.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_call(ExprNode *&current, int stage, int op)
{
	ExprNode *node = NULL;

	if(current == NULL)
		return false;

	node = new_expr_node(stage, op);

	if(Token.Data != NULL)
	{
		node->call.fn = *((FUNCTION_PTR)Token.Data);
		(void)POVFPU_GetFunctionAndReference(node->call.fn);
	}
	else
		node->call.fn = 0;
	node->call.token = Token.Function_Id;
	node->call.name = POV_STRDUP(Token.Token_String);
	while(current->child != NULL)
		current = current->child;

	current->child = node;
	node->parent = current;
	current = node;

	if(expr_get_token() != LEFT_PAREN_TOKEN)
		Expectation_Error("(");

	current->child = node = parse_expr();
	while(expr_get_token() == COMMA_TOKEN)
	{
		node->next = parse_expr();
		node->next->parent = node->parent;
		node = node->next;
	}

	if(Token.Token_Id != RIGHT_PAREN_TOKEN)
		Expectation_Error(")");

	return true;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_put
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that adds a new node in the
*   current location in the tree.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_put(ExprNode *&current, int stage, int op)
{
	ExprNode *node = NULL;

	if(current == NULL)
		return false;

	node = new_expr_node(stage, op);

	if(op == OP_CONSTANT)
	{
		node->number = Token.Token_Float;
	}
	else
	{
		node->variable = POV_STRDUP(Token.Token_String);
	}

	if(current->child != NULL)
		return false;

	current->child = node;
	node->parent = current;

	return true;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_new
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that creates a new expression
*   or subexpression.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_new(ExprNode *&current, int /*stage*/, int /*op*/)
{
	ExprNode *node = NULL;

	node = parse_expr();
	if(node == NULL)
		return false;

	current->child = node;
	node->parent = current;
	node->stage = 10000; // needs to be higher than any other stage for expr_grow to work [trf]

	return true;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_ret
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that marks the end of parsing
*   a expression or subexpression.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_ret(ExprNode *&, int, int)
{
	Unget_Token();

	return false;
}


/*****************************************************************************
*
* FUNCTION
*
*   expr_err
*
* INPUT
*
*   current - current poistion in expression tree
*   stage - stage/precedence of operation
*   op - operation
*   
* OUTPUT
*   
* RETURNS
*
*   bool - continue to parse expression?
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Expression parser manipulation function that terminates all parsing
*   and outputs a parse error message.
*
* CHANGES
*
*   -
*
******************************************************************************/

bool expr_err(ExprNode *&, int stage, int)
{
	int i;

	if(stage == 35)
		PossibleError("Suspicious identifier found in function!\n"
		              "If you want to call a function make sure the function you call has been declared.\n"
		              "If you call an internal function, make sure you have included 'function.inc'.");

	for(i = 0; (expr_parser_error_table[i].stage >= 0) && (expr_parser_error_table[i].expected != NULL); i++)
	{
		if(expr_parser_error_table[i].stage == stage)
			Expectation_Error(expr_parser_error_table[i].expected);
	}

	Expectation_Error("valid function expression");

	// unreachable, Expectation_Error stops parsing
	return false;
}


/*****************************************************************************
*
* FUNCTION
*
*   optimise_expr
*
* INPUT
*
*   node - root node of the expression (sub-) tree to optimise
*   
* OUTPUT
*   
* RETURNS
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Optimised an expression (sub-) tree.  Currently it only combines
*   constants next to each other.  Other optimisations are still waiting
*   to be implemented.
*
* CHANGES
*
*   -
*
******************************************************************************/

void optimise_expr(ExprNode *node)
{
	ExprNode *left,*right,*ptr,*temp;
	DBL result;
	bool have_result;
	int op,cnt;

	if(node == NULL)
		return;

	if(node->op == OP_CALL)
	{
		if(node->call.token == POW_TOKEN)
		{
			node->op = OP_FIRST;
			POV_FREE(node->call.name);
			if(node->child != NULL)
			{
				node->child->op = OP_LEFTMOST;
				if(node->child->next != NULL)
				{
					node->child->next->op = OP_POW;
					node->child->next->prev = node->child;
				}
			}
		}
	}

	if(node->op < OP_FIRST) // using switch statement might be better [trf]
	{
		ptr = node->next;
		if(ptr != NULL)
		{
			if(ptr->op == OP_NEG)
			{
				op = ptr->op;
				cnt = 0;
				for(ptr = node->next; ptr != NULL; ptr = ptr->next)
				{
					cnt++;
					if(ptr->child != NULL)
						break;
				}

				if(ptr != NULL)
				{
					optimise_expr(ptr->child);
					if(ptr->child != NULL)
					{
						left = ptr->child;
						if(left->op == OP_CONSTANT)
						{
							ptr->child = NULL;

							if(node->next != NULL)
								FNSyntax_DeleteExpression(node->next);

							if(op == OP_NEG)
							{
								if((cnt % 2) == 0)
									node->number = (left->number);
								else
									node->number = -(left->number);
							}
							POV_FREE(left);
							node->op = OP_CONSTANT;
							node->child = NULL;
							node->prev = NULL;
							node->next = NULL;
							return; // early exit
						}
					}
				}
			}
		}

		optimise_expr(node->child);
		for(ptr = node->next; ptr != NULL; ptr = ptr->next)
		{
			left = ptr->prev->child;
			right = ptr->child;

			if((right != NULL) && (ptr->op == OP_SUB))
			{
				if(right->op == OP_CONSTANT)
				{
					ptr->op = OP_ADD;
					right->number = -right->number;
				}
			}

			optimise_expr(right);

			if((left != NULL) && (right != NULL) &&
			   (((ptr->op != OP_MUL) && (ptr->op != OP_DIV)) ||
			    !left_subtree_has_variable_expr(ptr)))
			{
				if((left->op == OP_CONSTANT) && (right->op == OP_CONSTANT))
				{
					have_result = true;

					switch(ptr->op)
					{
						case OP_CMP_EQ:
							result = (left->number == right->number);
							break;
						case OP_CMP_NE:
							result = (left->number != right->number);
							break;
						case OP_CMP_LT:
							result = (left->number < right->number);
							break;
						case OP_CMP_LE:
							result = (left->number <= right->number);
							break;
						case OP_CMP_GT:
							result = (left->number > right->number);
							break;
						case OP_CMP_GE:
							result = (left->number >= right->number);
							break;
						case OP_ADD:
							result = (left->number + right->number);
							break;
						case OP_SUB:
							result = (left->number - right->number);
							break;
						case OP_OR:
							result = (DBL)(((DBL)((((DBL)(left->number != 0)) + ((DBL)(right->number != 0))))) != 0); // match VM code
							break;
						case OP_MUL:
							result = (left->number * right->number);
							break;
						case OP_DIV:
							result = (left->number / right->number);
							break;
						case OP_AND:
							result = (DBL)((((DBL)(left->number != 0)) * ((DBL)(right->number != 0)))); // match VM code
							break;
						case OP_POW:
							result = pow(left->number, right->number);
							break;
						default:
							have_result = false;
							break;
					}

					if(have_result == true)
					{
						temp = ptr;
						ptr->prev->next = ptr->next;
						if(ptr->next != NULL)
							ptr->next->prev = ptr->prev;
						ptr = ptr->prev;
						POV_FREE(temp->child);
						POV_FREE(temp);
						left->number = result;
					}
				}
			}
		}
		if((node->next == NULL) && (node->child != NULL) && (node->op < OP_FIRST))
		{
			if((node->child->op == OP_CONSTANT) && (node->child->next == NULL))
			{
				node->number = left->number;
				node->op = OP_CONSTANT;
				POV_FREE(node->child);
				node->child = NULL;
			}
		}
	}
	else
	{
		optimise_expr(node->child);

		optimise_call(node);

		if((node->child != NULL) && (node->op < OP_FIRST))
		{
			if((node->child->op == OP_CONSTANT) && (node->child->next == NULL))
			{
				node->number = node->child->number;
				POV_FREE(node->child);
				node->child = NULL;
				node->op = OP_CONSTANT;
			}
		}
	}
}


/*****************************************************************************
*
* FUNCTION
*
*   optimise_call
*
* INPUT
*
*   node - node of a function call
*   
* OUTPUT
*   
* RETURNS
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Optimises a function call if it has only constant arguments
*
* CHANGES
*
*   -
*
******************************************************************************/

void optimise_call(ExprNode *node)
{
	DBL result = 0.0;
	bool have_result = true;;

	if(node->op != OP_CALL)
		return;
	if(node->child == NULL)
		return;
	if(node->child->op != OP_CONSTANT)
		return;

	switch(node->call.token)
	{
		case SIN_TOKEN:
			result = sin(node->child->number);
			break;
		case COS_TOKEN:
			result = cos(node->child->number);
			break;
		case TAN_TOKEN:
			result = tan(node->child->number);
			break;
		case ASIN_TOKEN:
			result = asin(node->child->number);
			break;
		case ACOS_TOKEN:
			result = acos(node->child->number);
			break;
		case ATAN_TOKEN:
			result = atan(node->child->number);
			break;
		case SINH_TOKEN:
			result = sinh(node->child->number);
			break;
		case COSH_TOKEN:
			result = cosh(node->child->number);
			break;
		case TANH_TOKEN:
			result = tanh(node->child->number);
			break;
		case ASINH_TOKEN:
			result = asinh(node->child->number);
			break;
		case ACOSH_TOKEN:
			result = acosh(node->child->number);
			break;
		case ATANH_TOKEN:
			result = atanh(node->child->number);
			break;
		case ABS_TOKEN:
			result = fabs(node->child->number);
			break;
		case RADIANS_TOKEN:
			result = node->child->number * M_PI / 180.0;
			break;
		case DEGREES_TOKEN:
			result = node->child->number * 180.0 / M_PI;
			break;
		case FLOOR_TOKEN:
			result = floor(node->child->number);
			break;
		case INT_TOKEN:
			result = (int)(node->child->number);
			break;
		case CEIL_TOKEN:
			result = ceil(node->child->number);
			break;
		case SQRT_TOKEN:
			result = sqrt(node->child->number);
			break;
		case EXP_TOKEN:
			result = exp(node->child->number);
			break;
		case LN_TOKEN:
			if(node->child->number > 0.0)
				result = log(node->child->number);
			else
				Error("Domain error in 'ln'.");
			break;
		case LOG_TOKEN:
			if(node->child->number > 0.0)
				result = log10(node->child->number);
			else
				Error("Domain error in 'log'.");
			break;
		case MIN_TOKEN:
			have_result = false;
			break;
		case MAX_TOKEN:
			have_result = false;
			break;
		case ATAN2_TOKEN:
			have_result = false;
			break;
		case POW_TOKEN:
			have_result = false;
			break;
		case MOD_TOKEN:
			have_result = false;
			break;
		case SELECT_TOKEN:
			have_result = false;
			break;
		case FUNCT_ID_TOKEN:
			have_result = false;
			break;
		case VECTFUNCT_ID_TOKEN:
			have_result = false;
			break;
		default:
			have_result = false;
			break;
	}

	if(have_result == true)
	{
		POV_FREE(node->call.name);
		node->number = result;
		node->op = OP_CONSTANT;
		POV_FREE(node->child);
		node->child = NULL;
	}
}


/*****************************************************************************
*
* FUNCTION
*
*   right_subtree_has_variable_expr
*
* INPUT
*
*   node - root node of the (sub-) tree to search for variables
*   
* OUTPUT
*   
* RETURNS
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Searches an expression tree to determine if it contains any variables
*
* CHANGES
*
*   -
*
******************************************************************************/

bool right_subtree_has_variable_expr(ExprNode *node)
{
	if(node == NULL)
		return false;

	for(ExprNode *i = node; i != NULL; i = i->next)
	{
		if(i->op == OP_VARIABLE)
			return true;

		if(i->child != NULL)
		{
			if(right_subtree_has_variable_expr(i->child) == true)
				return true;
		}
	}

	return false;
}


/*****************************************************************************
*
* FUNCTION
*
*   left_subtree_has_variable_expr
*
* INPUT
*
*   node - root node of the (sub-) tree to search for variables
*   
* OUTPUT
*   
* RETURNS
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Searches an expression tree to determine if it contains any variables
*
* CHANGES
*
*   -
*
******************************************************************************/

bool left_subtree_has_variable_expr(ExprNode *node)
{
	if(node == NULL)
		return false;

	for(ExprNode *i = node; i != NULL; i = i->prev)
	{
		if(i->op == OP_VARIABLE)
			return true;

		if(i->child != NULL)
		{
			if(right_subtree_has_variable_expr(i->child) == true)
				return true;
		}
	}

	return false;
}


/*****************************************************************************
*
* FUNCTION
*
*   dump_expr
*
* INPUT
*
*   f - file to dump to
*   node - root node of the (sub-) tree to write to file
*   
* OUTPUT
*   
* RETURNS
*
* AUTHOR
*
*   Thorsten Froehlich
*   
* DESCRIPTION
*
*   Write an expression tree in inorder notation to a file. Useful for
*   debugging the function parser.
*
* CHANGES
*
*   -
*
******************************************************************************/

void dump_expr(FILE *f, ExprNode *node)
{
	if(node->op == OP_FIRST)
		fprintf(f, "[");
	else
		fprintf(f, "(");

	fflush(f);

	for(ExprNode *i = node; i != NULL; i = i->next)
	{
		switch(i->op)
		{
			case OP_CONSTANT:
				fprintf(f, "%f", (float)(i->number));
				break;
			case OP_VARIABLE:
				fprintf(f, "%s", i->variable);
				break;
			case OP_DOT:
				fprintf(f, ".");
				break;
			case OP_MEMBER:
				fprintf(f, "%s", i->variable);
				break;
			case OP_CALL:
				fprintf(f, "fn%d", (int)(i->call.fn));
				break;
			case OP_CMP_EQ:
				fprintf(f, " == ");
				break;
			case OP_CMP_NE:
				fprintf(f, " != ");
				break;
			case OP_CMP_LT:
				fprintf(f, " < ");
				break;
			case OP_CMP_LE:
				fprintf(f, " <= ");
				break;
			case OP_CMP_GT:
				fprintf(f, " > ");
				break;
			case OP_CMP_GE:
				fprintf(f, " >= ");
				break;
			case OP_ADD:
				fprintf(f, " + ");
				break;
			case OP_SUB:
				fprintf(f, " - ");
				break;
			case OP_OR:
				fprintf(f, " | ");
				break;
			case OP_MUL:
				fprintf(f, " * ");
				break;
			case OP_DIV:
				fprintf(f, " / ");
				break;
			case OP_AND:
				fprintf(f, " & ");
				break;
			case OP_POW:
				fprintf(f, " ^ ");
				break;
			case OP_NEG:
				fprintf(f, " -");
				break;
			case OP_NOT:
				fprintf(f, " !");
				break;
			default:
				break;
		}

		fflush(f);

		if(i->child != NULL)
			dump_expr(f, i->child);
	}

	if(node->op == OP_FIRST)
		fprintf(f, "]");
	else
		fprintf(f, ")");

	fflush(f);
}

END_POV_NAMESPACE
